{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "313bc333-1942-47d7-83a0-2e3370caf7d0",
   "metadata": {},
   "source": [
    "https://leetcode.com/problems/next-permutation/\n",
    "\n",
    "\n",
    "Time Limit Exceeded\n",
    "\n",
    "\n",
    "```python\n",
    "from itertools import permutations\n",
    "\n",
    "class Solution:\n",
    "    def nextPermutation(self, nums: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        #8:54\n",
    "        all_possibilitys = [list(one) for one in set(permutations(nums))]\n",
    "        all_possibilitys.sort()\n",
    "        #print(all_possibilitys)\n",
    "        changed = False\n",
    "        for index, one in enumerate(all_possibilitys):\n",
    "            if one == nums:\n",
    "                if (index < len(all_possibilitys) - 1):\n",
    "                    new = all_possibilitys[index + 1]\n",
    "                    #print(new)\n",
    "                    for i, value in enumerate(new):\n",
    "                        nums[i] = value\n",
    "                    changed = True\n",
    "                    break\n",
    "        if (changed == False):\n",
    "            if (len(all_possibilitys) > 0):\n",
    "                for i, value in enumerate(all_possibilitys[0]):\n",
    "                    nums[i] = value\n",
    "        #8:57\n",
    "        #debug until 9:01\n",
    "```\n",
    "\n",
    "___\n",
    "\n",
    "You never know what could be the end of your life if you do the right thing.\n",
    "\n",
    "Never give up.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "dabf0324-090b-4dc5-b2c0-07f3b99be35a",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 79,
   "id": "42d02cfd-e0ab-45a3-b7c0-2b8b5ae0dfdc",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 1, 5]\n"
     ]
    }
   ],
   "source": [
    "from itertools import permutations\n",
    "\n",
    "class Solution:\n",
    "    def nextPermutation(self, nums: list[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        # 2022-12-02 05:00\n",
    "        def find_it_2():\n",
    "            the_first_number_list = []\n",
    "            the_number_list = []\n",
    "            \n",
    "            nums_sorted = list(sorted(nums.copy()))\n",
    "            all_possibilitys = permutations(nums_sorted)\n",
    "            ready_to_capture = False\n",
    "            for index, one in enumerate(all_possibilitys):\n",
    "                if index == 0:\n",
    "                    the_first_number_list = list(one)\n",
    "    \n",
    "                if one == tuple(nums):\n",
    "                    #print(\"previous: \", one)\n",
    "                    ready_to_capture = True\n",
    "    \n",
    "                if ready_to_capture == True:\n",
    "                    #print(\"got the next: \", one)\n",
    "                    the_number_list = list(one)\n",
    "    \n",
    "                    #print(str(the_number_list), str(nums))\n",
    "                    if str(the_number_list) > str(nums):\n",
    "                        break\n",
    "                    elif str(the_number_list) == str(nums):\n",
    "                        the_number_list = []\n",
    "                        ready_to_capture == False\n",
    "                    else:\n",
    "                        the_number_list = []\n",
    "                        ready_to_capture == False\n",
    "        \n",
    "            if len(the_number_list) == 0:\n",
    "                the_number_list = the_first_number_list\n",
    "    \n",
    "            return the_number_list\n",
    "\n",
    "        the_number_list = find_it_2()\n",
    "        print(the_number_list)\n",
    "        # 2022-12-02 08:1\n",
    "\n",
    "solution = Solution()\n",
    "solution.nextPermutation([5, 1, 1])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "255db9db-3288-4055-8b77-caff6e736697",
   "metadata": {},
   "source": [
    "# Permutation Test"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "f8a887ca-56c3-4d8e-92d7-726ca3a3bcf9",
   "metadata": {},
   "outputs": [],
   "source": [
    "from pprint import pprint"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "id": "2242b093-2d53-45d3-be39-e4f397bd51ce",
   "metadata": {},
   "outputs": [],
   "source": [
    "a_list = [1,2,3]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "id": "9a2307b5-9cce-4b72-a1a5-82486c69a188",
   "metadata": {},
   "outputs": [],
   "source": [
    "from itertools import permutations"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "id": "441ad567-4654-4311-822c-fa25d84bded1",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)]\n"
     ]
    }
   ],
   "source": [
    "pprint(list(permutations(a_list)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "id": "e7d4b07b-2498-470a-a135-83a45a5d009b",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]\n"
     ]
    }
   ],
   "source": [
    "def my_permutation_function(a_list):\n",
    "    if len(a_list) == 0:\n",
    "        return []\n",
    "    elif len(a_list) == 1:\n",
    "        return [[a_list[0]]]\n",
    "    else:\n",
    "        temp_list = []\n",
    "        for index, element in enumerate(a_list):\n",
    "            rest_elements = a_list[:index] + a_list[index+1:]\n",
    "            for another_element in my_permutation_function(rest_elements):\n",
    "                if type(another_element) is list:\n",
    "                    # when recursive function return a list that has multiple elements inside: [x1, x2, x3]\n",
    "                    temp_list.append([element] + another_element)\n",
    "                else:\n",
    "                    # when recursive function return a list that only got one element inside: [x]\n",
    "                    temp_list.append([element] + [another_element])\n",
    "        return temp_list\n",
    "\n",
    "print(my_permutation_function(a_list))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "id": "32000d32-9c0a-4820-85e8-7c3d646cff7d",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]\n"
     ]
    }
   ],
   "source": [
    "def my_permutation_function2(a_list):\n",
    "    if len(a_list) == 0:\n",
    "        yield []\n",
    "    elif len(a_list) == 1:\n",
    "        yield [[a_list[0]]]\n",
    "    else:\n",
    "        for index, element in enumerate(a_list):\n",
    "            rest_elements = a_list[:index] + a_list[index+1:]\n",
    "            for another_element in my_permutation_function(rest_elements):\n",
    "                if type(another_element) is list:\n",
    "                    # when recursive function return a list that has multiple elements inside: [x1, x2, x3]\n",
    "                    yield [element] + another_element\n",
    "                else:\n",
    "                    # when recursive function return a list that only got one element inside: [x]\n",
    "                    yield [element] + [another_element]\n",
    "\n",
    "print(list(my_permutation_function2(a_list)))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "538e5ef3-11cd-4292-ab9a-c7607efafaa9",
   "metadata": {},
   "source": [
    "# Lexicographically Comparation Test"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 62,
   "id": "756179c0-74c9-4364-bfc1-df01c36cc7d5",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 62,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "\"[1, 5, 1]\" < \"[1, 1, 5]\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 63,
   "id": "c3641d62-58d4-45b8-a977-89000a907d1d",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 63,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "\"[1, 5, 1]\" < \"[5, 1, 1]\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 64,
   "id": "661c6c3f-97f9-4fba-b579-470c3f3dc86e",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 64,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "\"(1, 5, 1)\" < \"(1, 1, 5)\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 65,
   "id": "50f6ddd0-251f-4841-9153-5fe3df5f39f8",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 65,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "\"(1, 5, 1)\" < \"(5, 1, 1)\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "544541d5-da56-44dd-b4ed-c91410478f9f",
   "metadata": {},
   "outputs": [],
   "source": [
    "\"[1, 1, 5]\" > \"[5, 1, 1]\" #should be true according to leetcode, but i'm not sure. \n",
    "\n",
    "# I think python is right, leetcode is wrong here\n",
    "# So I won't try to solve this problem again"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "d88dce9e-e064-485b-9163-07fb529c63e9",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.10.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}